// 买卖股票的最佳时机

// 动态规划
// 贪心

// 动态规划(超时)
// 状态定义 : dp[i][j] : 第i天买入,第j天卖出可获得最大利润
// 状态转移方程 : 
// 当天买当天卖 -> 0
// dp[i][0] = 0
// dp[0][j] = nums[j]
// dp[i][j] = max(dp[i-1][j], price[j]-price[i]) // 前一天买第j天卖和当天买第j天卖哪个利润高
// 初始化 : 
// dp[0][0] = 0
// dp[1~size-1][0] = 0
// dp[0][1~size-1] = nums[j]
// 填表顺序 -> 从左向右从上向下
// 返回结果 : dp[size-1][size-1]
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int size = prices.size();
        std::vector<vector<int>> dp(size, vector<int>(size, 0));
        dp[0][0] = 0;
        for(int i = 1; i < size; ++i)
        {
            dp[i][0] = 0;
        }
        for(int j = 1; j < size; ++j)
        {
            dp[0][j] = prices[j] - prices[0];
        }
        for(int i = 1; i < size; ++i)
        {
            for(int j = i; j < size; ++j)
            {
                dp[i][j] = max(max(dp[i-1][j], prices[j] - prices[i]), dp[i-1][j-1]);
            }
        }
        return dp[size-1][size-1];
    }
};

// 贪心
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxprofit = 0, minprice = INT_MAX;
        for(auto& price : prices)
        {
            maxprofit = max(maxprofit, price - minprice);
            minprice = min(minprice, price);
        }
        return maxprofit;
    }
};
